package com.yequan.leetcode.array.maxarea_11;

import java.util.PriorityQueue;

/**
 * @author : Administrator
 * @date : 2020/3/14
 */
public class RecodeMaxArea {

    public static void main(String[] args) {
        RecodeMaxArea recodeMaxArea = new RecodeMaxArea();
        DoublePointer doublePointer = new DoublePointer();
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        int maxArea = doublePointer.maxArea5(height);
        System.out.println(maxArea);
    }

    /**
     * 左右夹逼法:
     * <p>
     * <p>
     * 核心思想:  maxArea = 有效高度(较小的高度) * 位置差
     * 用两根指针分别从数组两端往中间移动:
     * 移动高度较大的指针: 移动高度较大的指针不会改变有效高度,同时位置差变小,则maxArea一定变小,不行
     * 移动高度较大的指针: 移动高度较小的指针将改变有效高度,使有效高度变大,虽然位置差变小,但是maxArea变大的可能是存在的
     * <p>
     * 得出结论:
     * 用两根指针分别从数组两端开始往中间移动,高度较小的指针往中间移动一位,直到两端指针重合
     * <p>
     * 复杂度:
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    public static class DoublePointer {

        public int maxArea1(int[] height) {
            if (null == height || height.length == 0) {
                return 0;
            }
            int left = 0;
            int right = height.length - 1;
            int maxArea = 0;
            while (left < right) {
                maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
                if (height[left] < height[right]) {
                    left++;
                } else {
                    right--;
                }
            }
            return maxArea;
        }

        public int maxArea2(int[] height) {
            if (null == height || height.length == 0) {
                return 0;
            }
            int maxArea = 0;
            int left = 0;
            int right = height.length - 1;
            while (left < right) {
                maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
                if (height[left] < height[right]) {
                    left++;
                } else {
                    right--;
                }
            }
            return maxArea;
        }

        public int maxArea3(int[] height) {
            if (null == height || height.length == 0) {
                return 0;
            }
            int maxArea = 0;
            int left = 0;
            int right = height.length - 1;
            while (left < right) {
                maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
                if (height[left] < height[right]) {
                    left++;
                } else {
                    right--;
                }
            }
            return maxArea;
        }

        public int maxArea4(int[] height) {
            if (null == height || height.length == 0) {
                return 0;
            }
            int maxArea = 0;
            int left = 0;
            int right = height.length - 1;
            while (left < right) {
                maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
                if (height[left] < height[right]) {
                    left++;
                } else {
                    right--;
                }
            }
            return maxArea;
        }

        public int maxArea5(int[] height) {
            if (null == height || height.length == 0) {
                return 0;
            }
            int maxArea = 0;
            for (int left = 0, right = height.length - 1; left < right; ) {
                int validHeight = height[left] < height[right] ? height[left++] : height[right--];
                maxArea = Math.max(maxArea, validHeight * (right - left + 1));
            }
            return maxArea;
        }

        public int maxArea6(int[] height) {
            if (null == height || height.length < 2) {
                return 0;
            }
            int left = 0;
            int right = height.length - 1;
            int maxArea = 0;
            while (left < right) {
                maxArea = height[left] < height[right]
                        ? Math.max(maxArea, (right - left) * height[left++])
                        : Math.max(maxArea, (right - left) * height[right--]);
            }
            return maxArea;
        }

    }

}
